
abstract class BinaryHeap<T extends Comparable<T>> {
    //Constructor
    public BinaryHeap() {} 
    //Returns if the heap is empty or not
    abstract public boolean isEmpty();
    //Returns the size, number of elements (=maxIndex+1), of the heap
    abstract public int size();
    //Just returns the top (largest value) without modifying the heap 
    abstract public T getTop(); 
    //Just returns the value at index i without modifying the heap 
    abstract public T get(int i);
    //Just puts this value at index i, and returns the old value at index i, 
    //without modifying the rest of the heap 
    abstract public T set(int i, T val);
    //Remove top, heapify and then return old top
    abstract public T removeTop();
    //Add element as last and then move up as long as it is bigger than its parent 
    abstract public void addElement(T val); 
    
    //Some public relations for binary trees (needed for printing only)
    //NOTE: The depth, D, is defined as being 1 at the top!! If tree is empty, 
    //N=0, then D=0. If there is only one element, N=1, (index=0) then D=1
    public int depth(int index) {
	//Number of elements in a complete, balanced, binary tree is 2^D - 1. 
        //Solve for N, then D = log2(N+1). To use an index change i=N+1. 
        //Take closest upper integer part of the answer  (using ceil())
	return (int)Math.ceil( log2((double)(index+2)) );
    }
    public int maxIndexInDepth(int depth) {    // = 2^D - 2  (assuming rootIndex = 0)
        return (int)Math.pow((double)2, (double)depth) - 2;
    }
    public int maxIndexInDepth(int depth, int rootIndex) { 
        int maxIndex = rootIndex;
        for (int i = 1; i < depth; i++) maxIndex = rightChild(maxIndex);
        return maxIndex;
    }
    public int minIndexInDepth(int depth) {    // = 2^(D-1) - 1  (assuming rootIndex = 0)
        return (int)Math.pow((double)2, (double)(depth-1)) - 1;
    }
    public int minIndexInDepth(int depth, int rootIndex) { 
        int minIndex = rootIndex;
        for (int i = 1; i < depth; i++) minIndex = leftChild(minIndex);
        return minIndex;
    }
    public int maxElementsInDepth(int depth) { // = 2^(D-1)
        return (int)Math.pow((double)2, (double)(depth-1));
    }
    public double space(double center, int depth) {  //Appropiate space between elements
	return 2*center/(maxElementsInDepth(depth)+1) - 2; // -2 since the element takes place also
    }
    public double log2(double x) { return Math.log(x)/Math.log(2.); }
    
    
    //Protected methods needed to represent the heap with an array
    protected int parent(int child) {
	return (child - 1)/2;
    }
    protected int leftChild(int parent) {
	return 2*parent + 1;
    }
    protected int rightChild(int parent) {
	return 2*parent + 2;
    }
    protected int largestChild(int parent, int N) {
	int li = leftChild(parent);
	int ri = rightChild(parent);
	if (li >= N) return -1;    //dessa 2 rader e 
	if (ri >= N) return li;    //mycket viktiga
	//if (m_heap[li] > m_heap[ri]) return li; 
	if (get(ri).compareTo(get(li)) < 0) return li;
	return ri;
    }
    protected void swapElements(int i, int j) { 
        set(j, set(i, get(j)));        
    }
}
